package dynamicprogramming;

/**
 * @Author: 海琳琦
 * @Date: 2022/3/5 2:21
 * https://leetcode-cn.com/problems/climbing-stairs/
 * 改为：一步一个台阶，两个台阶，三个台阶，.......，直到 m个台阶。每一阶可以重复使用,问有多少种不同的方法可以爬到楼顶呢？
 */
public class ClimbStairsI {

    /**
     * 层数看成背包容量，每次步数看成物品价值，m代表物品个数
     * dp[j]表示到达层数j的方法个数
     *
     * @param n
     * @return
     */
    public int climbStairs(int n, int m) {

        int[] dp = new int[n + 1];
        dp[0] = 1;
        //背包容量
        for (int j = 0; j <= n; j++) {
            //物品数
            for (int i = 1; i <= m; i++) {
                if (j - i > 0) {
                    dp[j] += dp[j - i];
                }
            }
        }
        return dp[n];
    }

    public static void main(String[] args) {

    }
}
